<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    栈（Stack） - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						栈（Stack）
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/03/11 00:56 上午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E6%A0%88%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>抽象数据类型栈的定义</h2>
<p>栈是限定只能在表的一端进行插入和删除运算的线性表。只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILE）的原则（<strong>是操作受限的线性表</strong>）</p>
<table>
<thead>
<tr>
<th>栈</th>
<th>s</th>
</tr>
</thead>
<tbody>
<tr>
<td>栈顶元素→</td>
<td>a<sub>n</sub></td>
</tr>
<tr>
<td> </td>
<td>a<sub>n-1</sub></td>
</tr>
<tr>
<td> </td>
<td>···</td>
</tr>
<tr>
<td> </td>
<td>a<sub>2</sub></td>
</tr>
<tr>
<td>栈底元素→</td>
<td>a<sub>1</sub></td>
</tr>
</tbody>
</table>
<ul>
<li>栈是仅在表尾进行插入、删除操作的线性表。表尾（<strong>即a<sub>n</sub>端</strong>）称为栈顶top，表头（<strong>即a<sub>1</sub>端</strong>）称为栈底base</li>
<li>插入元素到栈顶的操作，称为<strong>入栈</strong>。从栈底删除最后一个元素的操作，称为<strong>出栈</strong>。</li>
</ul>
<h2><a id="%E9%A1%BA%E5%BA%8F%E6%A0%88" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序栈</h2>
<h3><a id="%E9%A1%BA%E5%BA%8F%E6%A0%88%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序栈的定义</h3>
<pre class="line-numbers"><code class="language-c">typedef struct
{
    SElemType *base; //栈底
    SElemType *top; // 栈顶
    int stacksize;
} SqStack;
</code></pre>
<h4><a id="%E5%85%A5%E6%A0%88%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>入栈操作</h4>
<pre class="line-numbers"><code class="language-c">*top = e;
top++;
</code></pre>
<h4><a id="%E5%87%BA%E6%A0%88%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>出栈操作</h4>
<pre class="line-numbers"><code class="language-c">top--;
e = *top;
</code></pre>
<h3><a id="%E9%A1%BA%E5%BA%8F%E6%A0%88%E7%9A%84%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序栈的操作</h3>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#define TRUE 1
#define FALSE 0
#define STACKINITSIZE 100
#define STACKINICREMENT 10
typedef int Status;
typedef int SElemType;

typedef struct
{
    SElemType *base; //栈底
    SElemType *top;  // 栈顶
    int stacksize;
} SqStack;

//初始化栈
void InitStack(SqStack *S);
//销毁栈（将占用的空间全部释放）
void DestroyStack(SqStack *S);
//清空栈（清空栈所存储的内容）
void ClearStack(SqStack *S);
//判断栈空
Status StatusEmpty(SqStack S);
//获取长度
int StackLenght(SqStack S);
//获取栈顶
Status GetTop(SqStack S, SElemType *e);

//入栈
void Push(SqStack *S, SElemType e);
//出栈
void Pop(SqStack *S, SElemType *e);
//访问栈内元素
void StackTraverse(SqStack S);

int main()
{
    SqStack S;
    SElemType e;

    return 0;
}

//初始化栈
void InitStack(SqStack *S)
{
    S-&gt;base = (SElemType *)malloc(STACKINITSIZE * sizeof(SElemType)); //给栈分配空间
    if (!S-&gt;base)
    {
        printf(&quot;初始化失败&quot;);
        return;
    }
    S-&gt;top = S-&gt;base;             //指向栈顶的指针置于和栈底相同的位置
    S-&gt;stacksize = STACKINITSIZE; //栈的空间大小
}

//销毁栈（将占用的空间全部释放）
void DestroyStack(SqStack *S)
{
    free(S-&gt;base);
    S-&gt;top = S-&gt;base = NULL;
    S-&gt;stacksize = 0;
}

//清空栈（清空栈所存储的内容）
void ClearStack(SqStack *S)
{
    S-&gt;top = S-&gt;base;
}
//判断栈空
Status StatusEmpty(SqStack S)
{
    if (S.top == S.base)
        return TRUE;
    return FALSE;
}
//获取长度
int StackLenght(SqStack S)
{
    return S.top - S.base; // Top值（栈顶）总是空的，Top - 1得到栈顶
}
//获取栈顶
Status GetTop(SqStack S, SElemType *e)
{
    //判断栈是否为空
    if (S.top == S.base)
    {
        printf(&quot;栈为空\n&quot;);
        return FALSE;
    }
    e = S.top - 1;
    return TRUE;
}

//入栈
void Push(SqStack *S, SElemType e)
{
    if (S-&gt;top - S-&gt;base == S-&gt;stacksize)
    {
        S-&gt;base = (SElemType *)realloc(S-&gt;base, (S-&gt;stacksize + STACKINICREMENT) * sizeof(SElemType));
        if (S-&gt;base == NULL)
        {
            printf(&quot;扩容失败&quot;);
            return;
        }
        //扩容后base指向新地址，top不变，需要手动让top指向新地址
        S-&gt;top = S-&gt;base + S-&gt;stacksize;
        S-&gt;stacksize += STACKINICREMENT;
    }
    *(S-&gt;top) = e;
    S-&gt;top++;
}
//出栈
void Pop(SqStack *S, SElemType *e)
{
    if (S-&gt;top == S-&gt;base)
    {
        printf(&quot;栈空&quot;);
        return;
    }
    S-&gt;top--;
    *e = *(S-&gt;top);
}
//访问栈内元素
void StackTraverse(SqStack S)
{
    SElemType *cur = S.base;
    while (cur != S.top)
    {
        printf(&quot;%d &quot;, *cur);
        cur++;
    }
    printf(&quot;\n&quot;);
}
</code></pre>
<h2><a id="%E9%93%BE%E6%A0%88" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链栈</h2>
<h3><a id="%E9%93%BE%E6%A0%88%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链栈的定义</h3>
<pre class="line-numbers"><code class="language-c">typedef struct snode 
{
    SElemType data;
    struct snode *link;
} Snode;
</code></pre>
<p><img src="media/16469313928169/16470193133030.jpg" alt="" /></p>
<ul>
<li>链栈的定义和链表一致，但是链栈需要对栈顶进行频繁的操作，所以头结点不适用于链栈</li>
<li>链表的<strong>首元结点</strong>和<strong>尾结点</strong>对应链栈的<strong>栈顶</strong>和<strong>栈底</strong></li>
</ul>
<h4><a id="%E5%85%A5%E6%A0%88" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>入栈</h4>
<pre class="line-numbers"><code class="language-c">s -&gt; link = top;
top = s;
</code></pre>
<h4><a id="%E5%87%BA%E6%A0%88" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>出栈</h4>
<pre class="line-numbers"><code class="language-c">cur = top;
top = cur -&gt; link;
free(cur);
</code></pre>
<h3><a id="%E9%93%BE%E6%A0%88%E7%9A%84%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链栈的操作</h3>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
typedef int SElemType;

typedef struct Snode
{
    SElemType data;     //数据域
    struct Snode *next; //指针域
} Snode, *SqLisk;

//链栈初始化
SqLisk InitStack(SqLisk sqStack);
//判断链栈是否为空
int EmptyStack(SqLisk sqStack);
//获取链栈的长度
int StackLength(SqLisk sqStack);
//进栈操作
void Push(SqLisk sqStack, SElemType e);
//出栈操作
void Pop(SqLisk sqStack, SElemType *e);
//获取栈顶元素
void GetTop(SqLisk sqStack, SElemType *e);
//销毁栈
SqLisk ClearStack(SqLisk sqStack);
//打印栈内元素
void StackTraverse(SqLisk sqStack);

//链栈初始化
SqLisk InitStack(SqLisk sqStack)
{
    //相当于创建指向整个链表的头指针
    sqStack = (Snode *)malloc(sizeof(Snode));
    sqStack-&gt;next = NULL; //指针置空
    return sqStack;
}
//判断链栈是否为空
int EmptyStack(SqLisk sqStack)
{
    return sqStack-&gt;next == NULL;
}

//获取链栈的长度
int StackLength(SqLisk sqStack)
{
    int count = 0;
    Snode *p = sqStack-&gt;next;
    while (p)
    {
        count++;
        p = p-&gt;next;
    }
    return count;
}

//进栈操作[链栈不存在栈满的情况]
void Push(SqLisk sqStack, SElemType e)
{
    //创建新的栈节点
    Snode *newNode = (Snode *)malloc(sizeof(Snode));
    newNode-&gt;data = e;    //数据域
    newNode-&gt;next = NULL; //指针域
    //插入节点-将新的结点插入到首节点位置
    newNode-&gt;next = sqStack-&gt;next; //新节点指向原来的首节点
    sqStack-&gt;next = newNode;       //将新节点置为首节点
}

//出栈操作
void Pop(SqLisk sqStack, SElemType *e)
{
    //变量声明
    Snode *p;
    //判断是否栈空
    if (sqStack-&gt;next == NULL)
        return;
    //记录栈顶元素
    p = sqStack-&gt;next;
    *e = p-&gt;data; //反向传递元素值
    //出栈操作-将头指针指向首结点的下一个结点
    sqStack-&gt;next = p-&gt;next;
    //释方旧的结点的内存空间
    free(p);
}

//获取栈顶元素
void GetTop(SqLisk sqStack, SElemType *e)
{
    //判断是否栈空
    if (sqStack-&gt;next == NULL)
        return;
    //获取栈顶元素值
    *e = sqStack-&gt;next-&gt;data;
}

//销毁栈
SqLisk ClearStack(SqLisk sqStack)
{
    //逐一释放每个结点的内存空间
    Snode *p = NULL; //辅助指针
    while ((p = sqStack-&gt;next) != NULL)
    {
        sqStack-&gt;next = p-&gt;next;
        free(p);
    }
    //释放头指针
    free(sqStack);
    sqStack = NULL; //置为零[避免野指针]
    return sqStack;
}

//打印栈内元素
void StackTraverse(SqLisk sqStack)
{
    //辅助指针
    Snode *p = sqStack-&gt;next;
    while (p)
    {
        printf(&quot;%d &quot;, p-&gt;data);
        p = p-&gt;next;
    }
    printf(&quot;\n&quot;);
}

int main()
{
    SqLisk top;
    SElemType e;
    top = InitStack(top);
    //进栈操作
    Push(top, 10);
    Push(top, 20);
    Push(top, 30);
    Push(top, 40);
    //打印栈内元素值
    StackTraverse(top);
    Pop(top, &amp;e);
    printf(&quot;the element value is %d\n&quot;, e);
    //获取栈顶元素
    GetTop(top, &amp;e);
    printf(&quot;the top element is %d\n&quot;, e);
    //打印栈内元素值
    StackTraverse(top);
    //销毁栈
    top = ClearStack(top);
    return 0;
}
</code></pre>
<h2><a id="%E6%A0%88%E7%9A%84%E5%BA%94%E7%94%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>栈的应用</h2>
<h3><a id="%E6%95%B0%E5%88%B6%E8%BD%AC%E6%8D%A2%EF%BC%8810%E8%BF%9B%E5%88%B6%E8%BD%ACn%E8%BF%9B%E5%88%B6%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数制转换（10进制转n进制）</h3>
<p>将要转换的数据不断与进制数求余，将余数按顺序压入顺序栈中，然后按倒序进行出栈</p>
<pre class="line-numbers"><code class="language-c">void convert()
{
    SqStack S;
    SElemType e;
    int n = 1348;
    InitStack(&amp;S);
    while (n != 0)
    {
        Push(&amp;S, n % 8); //余数入栈
        n /= 8; //在c中，&quot;/=&quot;两边都是整数将进行整除运算，舍弃小数位
    }
    while (!StatusEmpty(S)) //倒序进行出栈，栈空时表示所有数都已经出栈
    {
        Pop(&amp;S, &amp;e);
        printf(&quot;%d&quot;, e);
    }
    printf(&quot;\n&quot;);
    DestroyStack(&amp;S);
}
</code></pre>
<h2><a id="%E6%A0%88%E4%B8%8E%E9%80%92%E5%BD%92" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>栈与递归</h2>
<p>栈有一个重要的应用，在程序设计语言中实现递归</p>
<h3><a id="%E9%98%B6%E4%B9%98%E5%87%BD%E6%95%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>阶乘函数</h3>
<p><img src="media/16469313928169/16471120866442.jpg" alt="" /></p>
<h3><a id="fibonacci%E6%95%B0%E5%88%97" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Fibonacci数列</h3>
<p><img src="media/16469313928169/16471121483855.jpg" alt="" /></p>
<h3><a id="%E6%B1%89%E8%AF%BA%E5%A1%94%EF%BC%88hanoi%EF%BC%89%E9%97%AE%E9%A2%98" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>汉诺塔（Hanoi）问题</h3>
<p><img src="media/16469313928169/16471129033202.jpg" alt="" /></p>
<pre class="line-numbers"><code class="language-c">void Hanoi(int n, char x, char y, char z)
{
    if (n == 1)
        move(x, 1, z);
    else
    {
        Hanoi(n - 1, x, y, z);
        move(x, n, z);
        Hanoi(n - 1, y, x, z);
    }
}
</code></pre>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  














<script src="asset/prism.js"></script>









</body>

</html>